﻿/*  
  Copyright 2007-2009 The NGenerics Team
 (http://code.google.com/p/ngenerics/wiki/Team)

 This program is licensed under the GNU Lesser General Public License (LGPL).  You should 
 have received a copy of the license along with the source code.  If not, an online copy
 of the license can be found at http://www.gnu.org/copyleft/lesser.html. 
*/

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Collections;

namespace NGenerics.DataStructures.Immutable
{

	/// <summary>
    /// A few utility methods that do not need access to the private state of a <see cref="Range"/>.
    /// </summary>
    public static class RangeExtensions
    {
        /// <summary>
        /// Checks whether a range has no elements. null is treated as empty.
        /// </summary>
        /// <param name="range">The range to check.</param>
        /// <returns>true is the argument is null or has no elements, false else</returns>
        public static bool IsEmpty(this Range range)
        {
            return (range ?? Range.Empty) == Range.Empty;
        }

        /// <summary>
        /// Checks whether two ranges have common elements.
        /// </summary>
        /// <param name="a">The first range. null is treated as empty range.</param>
        /// <param name="b">The second range. null is treated as empty range.</param>
        /// <returns>true, if the two ranges have common elements, false when there are none.</returns>
        public static bool Overlaps(this Range a, Range b)
        {
            if (a.IsEmpty() || b.IsEmpty())
            {
                return false;
            }
            return a.Contains(b.From) || a.Contains(b.Thru);
        }

        /// <summary>
        /// Returns the range of elements that both arguments have in common.
        /// </summary>
        /// <param name="a">The first range. null is treated as empty range.</param>
        /// <param name="b">The second range. null is treated as empty range.</param>
        /// <returns>a new Range or Range.Empty</returns>
        public static Range Intersect(this Range a, Range b)
        {
            if (a.IsEmpty() || b.IsEmpty())
            {
                return Range.Empty;
            }

            // return new range with biggest From and smallest Thru
            return Range.Create(
                a.From > b.From ? a.From : b.From,
                a.Thru < b.Thru ? a.Thru : b.Thru);
        }

        /// <summary>
        /// Returns a new Range containing all elements from both arguments. 
        /// This is only legal if the result would not have any holes.
        /// </summary>
        /// <param name="a">The first range. null is treated as empty range.</param>
        /// <param name="b">The second range. null is treated as empty range.</param>
        /// <returns>a new range containing the union of both ranges, if this is possible without creating a hole.</returns>
        /// <exception cref="ArgumentOutOfRangeException">The ArgumentOutOfRangeException is thrown if the result would contain holes.</exception>
        public static Range Merge(this Range a, Range b)
        {
            if (a.IsEmpty() && b.IsEmpty())
            {
                return Range.Empty;
            }
            else if (!a.IsEmpty() && b.IsEmpty())
            {
                return a;
            }
            else if (a.IsEmpty() && !b.IsEmpty())
            {
                return b;
            }
            else if (!a.Overlaps(b))
            {
                throw new ArgumentOutOfRangeException("b", "provided Ranges don't touch");
            }

            // return new range with smallest From and biggest Thru
            return Range.Create(
                a.From < b.From ? a.From : b.From,
                a.Thru > b.Thru ? a.Thru : b.Thru);
        }

        /// <summary>
        /// Creates the union of the given arguments. If the ranges overlap, a new range is created.
        /// </summary>
        /// <param name="a">The first range. null is treated as empty range.</param>
        /// <param name="b">The second range. null is treated as empty range.</param>
        /// <returns>a new range containing the union of both ranges</returns>
        public static IEnumerable<int> Union(this Range a, Range b)
        {
            if (a.IsEmpty() && b.IsEmpty())
            {
                return Range.Empty;
            }
            else if (!a.IsEmpty() && b.IsEmpty())
            {
                return a;
            }
            else if (a.IsEmpty() && !b.IsEmpty())
            {
                return b;
            }
            else if (a.Overlaps(b))
            {
                return a.Merge(b);
            }
            else
            {
                return System.Linq.Enumerable.Concat(a, b);
            }
        }

        // TODO: check other members of System.Linq.Enumerable for possible optimisations
    }


    /// <summary>
    /// An Range is a list of consecutive integers. The elements are sorted 
    /// ascendingly. The smallest (first) element is <see cref="From"/>, while 
    /// the biggest (last) element is <see cref="Thru"/>. This implementation 
    /// only stores the upper and lower bounds and finishes all operations 
    /// (except iteration) in O(1), that is, independent of the length of the 
    /// range.
    /// </summary>
    /// <remarks>
    /// Use the <see cref="Range.Create(int,int)"/> method to create new ranges.
    /// </remarks>
#if (!SILVERLIGHT)
    [Serializable]
#endif
    public sealed class Range : IList<int>
    {
        #region Globals

        private readonly int from;
        private readonly int thru;

        #endregion

        #region Construction

        /// <summary>
        /// Creates an <see cref="Range"/> from <paramref name="from"/> 
        /// through <paramref name="thru"/>. If this range would not contain 
        /// any elements (thru %lt; from), <see cref="Range.Empty"/> is returned.
        /// </summary>
        /// <param name="from">The smallest value of the new range.</param>
        /// <param name="thru">The largest value of the new range.</param>
        /// <returns>a new range or <see cref="Range.Empty"/></returns>
        public static Range Create(int from, int thru)
        {
            if (from <= thru)
            {
                return new Range(from, thru);
            }
            else
            {
                return Empty;
            }
        }

        private Range(int from, int thru)
        {
            if (thru < from && !(from == emptyFrom && thru == emptyThru && emptyRangeSingleton == null))
            {
                throw new ArgumentOutOfRangeException("thru", String.Format(CultureInfo.InvariantCulture, "thru ({0}) is smaller than from ({1})", thru, from));
            }
            this.from = from;
            this.thru = thru;
        }

        #endregion

        #region Properties

        /// <summary>The smallest value in this range.</summary>
        public int From { get { return from; } }

        /// <summary>The largest value in this range.</summary>
        public int Thru { get { return thru; } }

        #region Empty Range

        private const int emptyFrom = 0;
        private const int emptyThru = -1;
        private static readonly Range emptyRangeSingleton = new Range(emptyFrom, emptyThru);

        /// <summary>
        /// A singleton empty range.
        /// </summary>
        public static Range Empty { get { return emptyRangeSingleton; } }

        #endregion

        #endregion

        #region Helper functions

        private void GuardInRange(int item)
        {
            if (!Contains(item))
            {
                throw new IndexOutOfRangeException();
            }
        }

        #endregion

        #region IList<int> Members

        /// <summary>
        /// Returns the zero-based index of the specified item in this range.
        /// </summary>
        /// <param name="item">the item to check</param>
        /// <returns><paramref name="index"/> - <see cref="Range.From"/></returns>
        /// <exception cref="IndexOutOfRangeException">This exception is thrown when the item is not contained in this range.</exception>
        public int IndexOf(int item)
        {
            GuardInRange(item);
            return item - From;
        }

        void IList<int>.Insert(int index, int item)
        {
            throw new NotImplementedException();
        }

        void IList<int>.RemoveAt(int index)
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Returns the value at the specified index.
        /// </summary>
        /// <param name="index">The zero-based index.</param>
        /// <returns><see cref="Range.From"/> + <paramref name="index"/></returns>
        /// <exception cref="IndexOutOfRangeException">This exception is thrown when the item is not contained in this range.</exception>
        public int this[int index]
        {
            get
            {
                var result = From + index;
                GuardInRange(result);
                return result;
            }
        }

        int IList<int>.this[int index]
        {
            get
            {
                var result = From + index;
                GuardInRange(result);
                return result;
            }
            set
            {
                throw new NotImplementedException();
            }
        }

        #endregion

        #region ICollection<int> Members

        void ICollection<int>.Add(int item)
        {
            throw new NotImplementedException();
        }

        void ICollection<int>.Clear()
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Checks whether the specified item is within this Range
        /// </summary>
        /// <param name="item">the item to check for</param>
        /// <returns>true if the item is in this Range, false else</returns>
        public bool Contains(int item)
        {
            return From <= item && item <= Thru;
        }

        /// <summary>
        /// Copies the values from this Range into the specified array, starting at <paramref name="arrayIndex"/>.
        /// </summary>
        /// <param name="array">the array to copy to.</param>
        /// <param name="arrayIndex">the first index that will be written to.</param>
        /// <exception cref="IndexOutOfRangeException">if the target array is too small</exception>
        public void CopyTo(int[] array, int arrayIndex)
        {
            for (var i = From; i <= Thru; i++)
            {
                array[arrayIndex++] = i;
            }
        }

        /// <summary>
        /// Gets the number of elements in this range.
        /// </summary>
        public int Count
        {
            get { return Thru - From + 1; }
        }

        bool ICollection<int>.IsReadOnly
        {
            get { return true; }
        }

        bool ICollection<int>.Remove(int item)
        {
            throw new NotImplementedException();
        }

        #endregion

        #region IEnumerable<int> Members

        /// <summary>
        /// Creates an enumerator suitable for iteration over this range.
        /// </summary>
        /// <returns>A new Enumerator returning the numbers from <see cref="Range.From"/> up to and including <see cref="Range.Thru"/>.</returns>
        public IEnumerator<int> GetEnumerator()
        {
            for (var i = from; i <= thru; i++)
            {
                yield return i;
            }
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region Operator Overloads

        /// <summary>
        /// Compares the two Ranges based on their contents.
        /// </summary>
        /// <param name="left">The first range to compare.</param>
        /// <param name="right">The second range to compare.</param>
        /// <returns>true, if both ranges have the same contents; false, otherwise.</returns>
        public static bool operator ==(Range left, Range right)
        {
            // shortcut reference equality
            if (ReferenceEquals(left, right))
            {
                return true;
            }

            return ReferenceEquals(left, null) || left.Equals(right);
        }

        /// <summary>
        /// Compares the two Ranges based on their contents.
        /// </summary>
        /// <param name="left">The first range to compare.</param>
        /// <param name="right">The second range to compare.</param>
        /// <returns>false, if both ranges have the same contents; true, otherwise.</returns>
        public static bool operator !=(Range left, Range right)
        {
            return !(left == right);
        }

        #endregion

        #region Object Overrides

        /// <summary>
        /// Checks whether the specified range is equal to this range.
        /// </summary>
        /// <param name="obj">the other ranger</param>
        /// <returns>true if both ranges contain the same elements; false, otherwise</returns>
        public override bool Equals(object obj)
        {
            var other = obj as Range;
            if (other == null)
            {
                return false;
            }

            return From == other.From && Thru == other.Thru;
        }

        /// <summary>
        /// Returns a proper hash code for this range.
        /// </summary>
        /// <returns>a hash code calculated from the range's properties</returns>
        public override int GetHashCode()
        {
            return From ^ Thru;
        }

        /// <summary>
        /// Creates a concise, user-readable representation of this range
        /// </summary>
        /// <returns>a short string showing the upper and lower bound</returns>
        public override string ToString()
        {
            return String.Format(CultureInfo.InvariantCulture, "[{0}, {1}]", From, Thru);
        }

        #endregion
    }
}
